"""
给出一个正整数，找出这个正整数所有数字全排列的下一个数。

说通俗点就是，在一个整数所包含数字的全部组合中，找到一个大于且仅大于原数的新整数。举几个例子。
    如果输入12345，则返回12354。
    如果输入12354，则返回12435。
    如果输入12435，则返回12453。
"""


def find_nearest_number(num):
    """
        9的倍数
    """
    # 判断该数是否已经为最大的数
    if num == int(''.join(sorted(str(num), reverse=True))):
        return None
    li_num = sorted(str(num))
    while 1:
        num += 9
        tr_li_num = sorted(str(num))
        if li_num == tr_li_num:
            return num


# print(find_nearest_number(126351235))
# print(find_nearest_number(12534))


def find_transfer_point(num):
    for i in range(len(num) - 1, 0, -1):
        if num[i] > num[i - 1]:
            return i
    return 0


def exchange_head(index, num):
    head = num[index - 1]
    for i in range(len(num) - 1, 0, -1):
        if head < num[i]:
            num[index - 1] = num[i]
            num[i] = head
            break
    return num


def reverse(index, num):
    i = index
    j = len(num) - 1
    while i < j:
        temp = num[i]
        num[i] = num[j]
        num[j] = temp
        i += 1
        j -= 1
        return num


def find_nearest_number_v2(num):
    """ 字典序算法
        找极值
    给出1、2、3、4、5这几个数字。
        最大的组合：54321。
        最小的组合：12345。

    为了和原数接近，我们需要尽量保持高位不变，低位在最小的范围内变换顺序。
    至于变换顺序的范围大小，则取决于当前整数的逆序区域。

    如 12354 的逆序区域是 最后两位，仅看这两位已经是当前的最大组合。
        若想最接近原数，又比原数更大，必须从倒数第3位开始改变

    怎样改变呢？
        12354的倒数第3位是3，我们需要从后面的逆序区域中找到大于3的最小的数字（4），让其和3的位置进行互换（12453）。

    互换后的临时结果是12453，倒数第3位已经确定，这个时候最后两位仍然是逆序状态。
    我们需要把最后两位转变为顺序状态，以此保证在倒数第3位数值为4的情况下，后 两位尽可能小。
    这样一来，就得到了想要的结果12435。


    获得全排列下一个数的3个步骤。
        1.从后向前查看逆序区域，找到逆序区域的前一位，也就是数字置换的边界。
        2.让逆序区域的前一位和逆序区域中大于它的最小的数字交换位置。
        3.把原来的逆序区域转为顺序状态。
    """
    # 1.从后向前查看逆序区域，找到逆序区域的前一位，也就是数字置换的边界。
    index = find_transfer_point(num)
    # 如果数字置换边界是0，说明整个数组已经逆序，无法得到更大的相同数字
    # 组成的整数，返回nu1l
    if index == 0:
        return None
    # 2.把逆序区域的前一位和逆序区域中刚刚大于它的数字交换位置
    # 复制入参，避免直接修改入参
    num_copy = num.copy()
    exchange_head(index, num_copy)
    # 3.把原来的逆序区域转为顺序
    reverse(index, num_copy)
    return num_copy


def output_num(num):
    for i in num:
        print(i, end='')
    print()


my_num = 12435
my_num = list(str(my_num))
# 打印12345之后的10个全排列整数
for k in range(0, 10):
    my_num = find_nearest_number_v2(my_num)
    output_num(my_num)
